class Solution(object):
    def NumberOf1(self, n):
        """
        :type n: int
        :rtype: int
        """
        arr = [1 for i in range(31)]
        for i in range(1, 31):
            arr[i] = 2 * arr[i-1]
        binArr = [0 for i in range(32)]
    
        if n == 0 :
            return 0
        elif n > 0:
             max = 0
             for x in arr:
                max += x
             if n <= max :
                 binArr[31] = 0
                 for i in range(30,-1,-1):
                    if n >= arr[i] and n != 0 :
                        binArr[i] = 1
                        n = n - arr[i]
                    else :
                        binArr[i] = 0
        elif n < 0:
            min = 0
            for x in arr:
                min -= x
            binArr[31] = 1
            if n >= min :
                n = -n
                for i in range(30,-1,-1):
                    if n >= arr[i] and n != 0 :
                        binArr[i] = 1
                        n = n - arr[i]
                    else :
                        binArr[i] = 0
                # 反码
                for i in range(31):
                    if binArr[i] == 0:
                        binArr[i] = 1
                    elif binArr[i] == 1 :
                        binArr[i] = 0
                # 补码
                for i in range(31):
                    if binArr[i] == 0 :
                        binArr[i] = 1
                        break
                    elif binArr[i] == 1 :
                        binArr[i] = 0
        
        cnt = 0
        for x in binArr:
            if x == 1:
                cnt += 1
        return cnt